### 双指针技巧：
from typing import Dict, List, Tuple

from base import *
# 1. 合并2个有序链表
class Merge2ListNode(object):
    def solution(self,head1,head2):
        dummy = ListNode(-1)
        cur = dummy
        p1 = head1
        p2 = head2
        # 注意边界条件！
        while p1 is not None and p2 is not None:
            if p1.val < p2.val:
                cur.next=p1
                p1 = p1.next
            else:
                cur.next=p2
                p2 = p2.next
            cur=cur.next
        # 需要把剩余的接上
        if p1 is not None:
            cur.next = p1
        # 可能两者长度相同，所以不能写else
        if p2 is not None:
            cur.next = p2

        return dummy.next

    def test(self):
        list1 = [1, 5, 6, 8, 9]
        list2 = [2, 6, 7, 10]
        listnode1 = list_2_ListNode(list1)
        listnode2 = list_2_ListNode(list2)
        res = self.solution(listnode1, listnode2)
        tranverse_listnode(res)
        print("done!")
# 2. 给你一个无序的单链表，和一个给定值，将小于这个值的节点放在大于或等于这个值的节点前面，大的放后面，没有空间复杂度的要求
# 还有一个要求： 保留 两个分区中每个节点的初始相对位置（下面用链表就可以轻易做到）
class ResortListNode(object):
    def solution(self, head: ListNode, x: int) -> ListNode:
        # 存放小于 x 的链表的虚拟头结点: 虚拟头节点不进行遍历操作！
        dummy1 = ListNode(-1)
        # 存放大于等于 x 的链表的虚拟头结点
        dummy2 = ListNode(-1)
        # p1, p2 指针负责生成结果链表
        p1, p2 = dummy1, dummy2
        # p 负责遍历原链表，类似合并两个有序链表的逻辑
        # 这里是将一个链表分解成两个链表
        p = head
        while p:
            if p.val >= x:
                p2.next = p
                p2 = p2.next
            else:
                p1.next = p
                p1 = p1.next
            # 不能直接让 p 指针前进，
            # p = p.next
            # 断开原链表中的每个节点的 next 指针
            temp = p.next
            p.next = None
            p = temp
        # 连接两个链表
        p1.next = dummy2.next
        return dummy1.next
    def test(self):
        list1 = [6,3,9,5,9,1,3,4]
        target = 5
        head = list_2_ListNode(list1)
        res = self.solution(head,target)
        tranverse_listnode(res)
        print("done!")
# 3. 合并 k 个有序链表23
# 思路：适用最小堆先存放值，再一个一个pop做成链表
class MergeMultiListNode(object):
    def solution(self,headlist:List) -> ListNode:
        import heapq
        # 将有序链表都存入一个最小堆：
        min_heap = []
        for head in headlist:
            cur = head
            while cur:
                heapq.heappush(min_heap,cur.val)
                cur=cur.next
        # 再构建成链表：
        dummy = ListNode(-1)
        cur = dummy
        while min_heap:
            val = heapq.heappop(min_heap)
            new_node = ListNode(val)
            cur.next=new_node
            cur= cur.next
        return dummy.next
    def test(self):
        a = list_2_ListNode([1,5,3,4,1,2])
        b = list_2_ListNode([1,6,9,2,2,1])
        c = list_2_ListNode([5,5,3,6,4,1])
        lists = [a,b,c]
        res = self.solution(lists)
        tranverse_listnode(res)
# 4. 删除单链表的倒数第N个节点：
# 思路上有一个结论：倒数第N个节点就是第k-N+1个节点，k是链表的长度：
# 两个指针p1,p2:p2先走到正数第N个节点，然后两个指针一起走，p2走到表末尾指向空时p1就指向了目标点；删除第N个则需找到前一个节点
# 边界问题：可能出现极端情况：5个节点要删除倒数第5个节点：头节点传入dummy(双指针从虚拟节点开始遍历)
class Delete_N_ListNode(object):
    def solution(self,head:ListNode, N: int) -> ListNode:
        dummy=ListNode(-1)
        dummy.next = head
        p1,p2=dummy,dummy
        for i in range(N+1):# 找到第倒数N+1个节点
            p2=p2.next
        while p2:
            p1=p1.next
            p2=p2.next
        # 删除倒数第N个节点：
        p1.next=p1.next.next
        return dummy.next
    def test(self):
        head = list_2_ListNode([1,2,3,4])
        N=4
        res = self.solution(head,N)
        tranverse_listnode(res)
# 5. 找到链表的中点：
# 思路：快慢指针，1step，2step
# 边界条件是快指针指到最后一个节点或指向空时
# 简单题
class FindListNode_MidPoint(object):
    def solution(self,head):
        p1,p2=head,head
        while p2 and p2.next:
            p1=p1.next
            p2=p2.next.next
        return p1
    def test(self):
        head = list_2_ListNode([1,2,3,4,5,6])
        res = self.solution(head)
# 6. 判断一个链表中是否有环并找到这个环的起点：
# 思路：判断是否有环：可以用快慢指针，如果两个指针会相遇那就有环；
# 找环的起点相对麻烦一些
# 开始是start和end相同如何处理？ -> 先开始跑起来，那要是遇到长度小的链表怎么办？
# middle
class Circle_ListNode(object):
    def check_circle(self,head):
        # 先判断是否有环
        slow,fast = head,head
        while fast and fast.next: # 边界条件：注意：之后的快慢指针都这样处理，因为可能链表长度是1，就用不着快指针了
            slow = slow.next
            fast = fast.next.next
            if slow==fast:
                return 1
        return 0
    def find_starts(self,head):
        # 找链表环的起点：
        # 画图理解，高中物理题目：假设环的长度是k，快慢指针相遇时，快指针多走了k，假设起点到相遇点距离为m，则起点到环距离为k-m；
        # 此时让慢指针回到起点，快指针退化成1step，两者再次相遇时即在环的起点
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head  # 让慢指针回去, 本题是一定有环的
                while slow:
                    if slow == fast:
                        return slow
                    # 这里移动指针的步骤必须放在判断后面：因为有可能整个都是环[1,2]
                    slow = slow.next
                    fast = fast.next
        return None
    def test(self):
        head = make_circle_listnode([1,2], 1, 0)
        # no_cicle_head = list_2_ListNode([1,2,3,4])
        res = Circle_ListNode().check_circle(head)
        print('该链表是否有环：',res)
        res = self.find_starts(head)
        a = res
        print("找到了环的起点，其值为：", a.val)
# 7. 寻找链表的交点：
# 思路：相向而行：p1,p2分别从两个链表开始走，然后开始从对方的头开始，最后一定会在交点相遇；
# 为什么呢？ -> 因为最终路程相等了！amazing！
class Judge_the_Joint(object):
    def solution(self,headA,headB):
        p1=headA
        p2=headB
        # 需要同时进行链表的跳转，边界条件怎么做？ ！！ 看下面的思路：是从满足循环结束条件来的：默认了有交点
        # p1 指向 A 链表头结点，p2 指向 B 链表头结点
        p1, p2 = headA, headB
        while p1 != p2:
            # p1 走一步，如果走到 A 链表末尾，转到 B 链表
            p1 = headB if p1 is None else p1.next
            # p2 走一步，如果走到 B 链表末尾，转到 A 链表
            p2 = headA if p2 is None else p2.next
        return p1
    def create_crossed_two_listnode(self):
        nums1=[1,2,3,4,5]
        nums2=[2,3,4,5]
        # 链表的节点是不能有两个next指针的，所以相交之后一定都是共同的部分
        head1=list_2_ListNode(nums1)
        p1 = head1
        # 找到交点：
        while p1:
            if p1.val==3:
                cross=p1
                break
            p1=p1.next
        head2 = ListNode(2)
        cur = head2
        for num in nums2:
            newnode = ListNode(num)
            if newnode.val==3:
                cur.next=cross
                break
            cur.next=newnode
        return head1,head2
    def test(self):
        head1,head2=self.create_crossed_two_listnode()
        res = self.solution(head1,head2)
        print(res)

if __name__=="__main__":
    Judge_the_Joint().test()
    print('done!')


